// c++ standard libraries
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

// c libraries
#include <cmath>

using namespace std;

void MinCost(int L, int n, int *p);

void ShowCost(vector<vector<int>> c);

struct testCase {
    int L;
    int n;
    int *p;
};


int main() {

//    static_assert(false, "注意, 实验二的题目说明文档: exp2.pdf中说第二行输入n个切点p, 理论上切点是不包括头尾两个切点的"
//                         ", 但是在Moodle系统上实测的时候发现, 系统输入的p是带头尾两个切点的");

    testCase case1 = {
            .L = 7,
            .n = 4,
    };
    // 注意 头尾切点 0 和 7
    int case1_p[] = {0, 1, 3, 4, 5, 7};
    case1.p = case1_p;

    testCase case2 = {
            .L = 2000,
            .n = 77,
    };
    // 注意 头尾切点 0 和 2000
    int case2_p[] = {0, 1166, 299, 1574, 904, 274, 380, 1202, 1541, 819, 951,
                     794, 1183, 878, 1914, 1411, 1910, 765, 133, 917, 175,
                     1185, 1233, 1916, 1172, 279, 1437, 1504, 954, 173, 415,
                     502, 1597, 1044, 1800, 1029, 1939, 81, 1976, 1161, 25,
                     816, 659, 354, 267, 1302, 103, 615, 1588, 932, 1198,
                     1309, 1950, 524, 405, 218, 556, 735, 1072, 402, 542,
                     351, 1556, 454, 1841, 935, 48, 1446, 1958, 411, 1940,
                     1640, 619, 544, 1252, 84, 211, 782, 2000};
    case2.p = case2_p;

    MinCost(case1.L, case1.n, case1.p);
    MinCost(case2.L, case2.n, case2.p);

    return 0;
}

void MinCost(int L, int n, int *p) {
    // c[i][j] 表示从 i 切到 j 的成本, 则最终所求为c[0][7]
#include <climits>


    // 设置切点列表
    vector<int> cutpoints;
//    cutpoints.push_back(0);
    for (int i = 0; i < n + 2; i++)
        cutpoints.push_back(p[i]);
//    cutpoints.push_back(L);
    sort(cutpoints.begin(), cutpoints.end());

    // 下面可以用map(dict)更高效的实现, 但是我c++只是二把刀, 不如Python熟练
    // 切点索引
    int num_cutpoint = (int) cutpoints.size();
    vector<int> cutpoint2idx(cutpoints.at(num_cutpoint - 1) + 1, -1);
    int j = 0;
    for (int i = 0; i < num_cutpoint; i++)
        cutpoint2idx.at(cutpoints.at(i)) = j++;
    // 索引转切点
    j = 0;
    vector<int> idx2cutpoint(num_cutpoint, -1);
    for (int i = 0; i < (int) cutpoint2idx.size(); i++)
        if (cutpoint2idx.at(i) != -1)
            idx2cutpoint[j++] = i;


    vector<vector<int>> c(num_cutpoint, vector<int>(num_cutpoint, -1));

    // 主对角线填0
    for (int idx = 0; idx < num_cutpoint; idx++)
        c.at(idx).at(idx) = 0;
    for (int idx = 0; idx < num_cutpoint - 1; idx++)
        c.at(idx).at(idx + 1) = 0;

    // 填表
    for (int shift_right_range = 2; shift_right_range <= num_cutpoint; shift_right_range++) {
        for (int fill_row = 0; fill_row < num_cutpoint - shift_right_range + 1; fill_row++) {
            int fill_col = fill_row + shift_right_range - 1;
            if (c[fill_row][fill_col] == 0)
                continue;
            c[fill_row][fill_col] = INT_MAX;
            for (int k = fill_row + 1; k < fill_col; k++) {
                int t = c[fill_row][k] + c[k][fill_col] + idx2cutpoint[fill_col] - idx2cutpoint[fill_row];
                if (t < c[fill_row][fill_col])
                    c[fill_row][fill_col] = t;
            }
//            ShowCost(c);
        }
    }
//    ShowCost(c);
    cout << c[0][c.at(0).size() - 1] << endl;
}

void ShowCost(vector<vector<int>> c) {
    unsigned long rows = c.size();
    unsigned long cols = c.at(1).size();

    cout << "\t";
    for (int i = 0; i < cols; i++)
        cout << setw(5) << i << "-th";
    cout << endl;
    for (int i = 0; i < rows; i++) {
        cout << i << "-th:\t";
        for (int j = 0; j < cols; j++)
            cout << setw(5) << c.at(i).at(j) << "\t";
        cout << endl;
    }
    cout << endl;
}